﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.Trees
{
    public class BoundedArityTree<T> : IRootedTree<T>
    {

        private readonly T[] _tree;
        private readonly int _arity;
        private readonly int _rootIndex;
        private readonly T _token;
        private readonly EqualityComparison<T> _equalityComparison;

        /// <summary>
        /// 
        /// </summary>
        /// <param name="data"></param>
        /// <param name="arityTree"></param>
        /// <param name="arity"></param>
        /// <param name="rootIndex"></param>
        /// <param name="token">Represents a null element.</param>
        public BoundedArityTree(IEnumerable<T> data = null,
            BoundedArityTree<T> arityTree = null, int arity = 2, int rootIndex = 0, T token = default(T), EqualityComparison<T> equalityComparison = null)
        {
            data = data ?? Enumerable.Empty<T>();
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            if (arityTree == null)
            {
                _tree = data.ToArray();
                _arity = arity;
            }
            else
            {
                _tree = arityTree._tree;
                _arity = arityTree._arity;
            }

            _rootIndex = rootIndex;
            _token = token;
        }
        
        #region IRootedTree<T> members

        public T Root
        {
            get { return _tree[_rootIndex]; }
        }

        public virtual IEnumerable<T> Successors(T node)
        {
            if (_equalityComparison(node,_token))
                yield break;

            for(int i = _rootIndex; i < _tree.Length ;i++)
            {
                if (_equalityComparison(_tree[i],node))
                {
                    int firstChild = _arity * i + 1;
                    for (int j = firstChild; j < Math.Min(_tree.Length,firstChild + _arity); j++)
                        if (!_equalityComparison(_tree[j],_token))
                        {
                            yield return _tree[j];
                        }
                    yield break;
                }
            }
        }

        public virtual IEnumerable<T> Predecessors(T node)
        {
            if (_equalityComparison(node,_token))
                yield break;

            if (!_equalityComparison(_tree[_rootIndex],node))
            {
                for (int i = _rootIndex+1; i < _tree.Length; i++)
                {
                    if (_equalityComparison(_tree[i],node))
                    {
                        yield return _tree[(i - 1)/ _arity];
                    }
                }

            }
        }

        public virtual int InDegree(T elem)
        {
            return _equalityComparison(elem,_tree[_rootIndex]) ? 0 : 1;
        }

        public virtual int OutDegree(T elem)
        {
            return Successors(elem).Count();
        }

        // public IEnumerable<BoundedArityTree<T>> SubTrees()
        public virtual IEnumerable<IRootedTree<T>> SubTrees()
        {
            int firstChild = _arity * _rootIndex + 1;
            for (int i = firstChild; i < Math.Min(_tree.Length, firstChild + _arity); i++)
                if (!_equalityComparison(_tree[i],_token))
                    yield return Tree(_tree[i]);
        }

        //public BoundedArityTree<T> Tree(T root)
        public virtual IRootedTree<T> Tree(T root)
        {
            if (_equalityComparison(root,_token))
                return null;
            for(int i = _rootIndex; i < _tree.Length; i++)
                if (_equalityComparison(_tree[i],root))
                {
                    var data = new List<T> {root};
                    data.AddRange(Successors(root));
                    foreach (var successor in Successors(root))
                    {
                        FillTree(data, successor);
                    }
                    return new BoundedArityTree<T>(data, arity: _arity, token: _token);
                }
            return null;
        }

     
        #endregion

        private void FillTree(List<T> data, T value)
        {
            data.AddRange(Successors(value));
            foreach(var successor in Successors(value))
            {
               FillTree(data,successor);
            }
        }


        public override string ToString()
        {

            var sb = new StringBuilder(String.Format("{0} <{1}> [ ", GetType().Name, typeof(T).Name));

            foreach (T item in _tree)
            {
                if (!_equalityComparison(item,_token))
                    sb.Append(item + ",");
            }
            sb.Append(String.Format("], arity={0}, rootIndex={1})", _arity, _rootIndex));
            return sb.ToString();
            
        }

    }
}
